package main.Q1801_1900;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class Q1861_1870 {
    public static void main(String[] args) {
        System.out.println("Question1861：旋转盒子");
        System.out.println("Question1862：");
        System.out.println("Question1863：");
        System.out.println("Question1864：");
        System.out.println("Question1865：");
        System.out.println("Question1866：");
        System.out.println("Question1867：");
        System.out.println("Question1868：");
        System.out.println("Question1869：");
        System.out.println("Question1870：准时道道的列车最小时速");
    }
}

class Question1861 {
    public char[][] rotateTheBox(char[][] box) {
        int m = box.length, n = box[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = n - 1, range = n; j >= 0; j--) {
                char cur = box[i][j];
                if (cur == '#') {
                    box[i][j] = '.';
                    box[i][--range] = cur;
                } else if (cur == '*') {
                    range = j;
                }
            }
        }
        char[][] result = new char[n][m];
        for (int i = 0; i < m; i++) {
            int ansj = m - 1 - i;
            for (int j = 0; j < n; j++) {
                result[j][ansj] = box[i][j];
            }
        }
        return result;
    }
}

class Question1870 {
    public int minSpeedOnTime(int[] dist, double hour) {
        int n = dist.length;
        int maxSpeed = 1;
        // 前面n-1个元素，最少要用n-1小时，故取前n-1元素的最大值即可
        for (int i = 0; i < n - 1; i++) maxSpeed = Math.max(maxSpeed, dist[i]);
        // maxSpeed还需与最后一个元素的最大可能速度做比较
        maxSpeed = Math.max(maxSpeed, (int) (dist[n - 1] * 1.0d / (hour - n + 1)) + 1);
        int l = 0, r = maxSpeed + 1;
        while (l + 1 < r) {
            int c = l + (r - l) / 2;
            if (getTime(dist, c) <= hour) r = c;
            else l = c;
        }
        return r == maxSpeed + 1 ? -1 : r;
    }

    public double getTime(int[] dist, int speed) {
        double time = 0.0;
        int n = dist.length;
        for (int i = 0; i < n - 1; i++) time += (dist[i] - 1) / speed + 1;
        time += dist[n - 1] * 1.0d / speed;
        return time;
    }
}